import java.util.Comparator;
import java.util.PriorityQueue;

class GreaterIntCmp implements Comparator<Integer> {

    //使用比较器来建立大根堆.
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}

public class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        //虽然题目已经说了k>=0的,但是作为一名程序员,严谨是刻在骨子里的
        if(k <= 0){
            return ret;
        }

        GreaterIntCmp greaterIntCmp = new GreaterIntCmp();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(greaterIntCmp);
        //先将前K个创建为大根堆
        for(int i = 0;i < k;i++){
            maxHeap.offer(arr[i]);
        }

        //从k+1个元素开始,每次和堆顶元素进行比较
        for(int i = k;i < arr.length;i++){
            int top = maxHeap.peek();
            if(arr[i] < top){
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }

        //取出前K个进行返回
        for(int i = 0;i < k;i++){
            ret[i] = maxHeap.poll();
        }

        return ret;


    }



    /* //将前k个元素取出来建立一个大根堆
    private void createHeap(int[] arr,int k){
        for(int parent = (k - 1 - 1) / 2;parent >= 0;parent++){
            shiftDown(arr,parent,k);
        }
    }

     *//***
     *
     * @param arr
     * @param parent 每棵子树的根节点
     * @param length 每棵子树调整的结束节点
     *//*
    private void shiftDown(int[] arr,int parent,int length){
        int child = 2 * parent + 1;
        while(child < length){
            if(child + 1 < length && arr[child] < arr[child + 1]){
                child++;
            }

            if(arr[child] > arr[parent]){
                //交换根节点和节数节点
                swap(arr,parent,child);
                parent = child;
                child = 2 * parent + 1;
            }else {
                //说明已经是大根堆了,直接跳出循环就可以了;
                break;
            }
        }
    }

    //排序基本上离不开交换,写一个交换函数减少代码的冗余;
    private void swap(int[] arr,int i ,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    } */
}
